package LeetCode;

import java.util.Arrays;

public class FirstMissingPositive {
  public static int firstMissingPositive1(int[] A) {
    // Start typing your Java solution below
    // DO NOT write main() function

    //put i to A[i-1], so the array looks like: 1, 2, 3, ...

    for (int i = 0; i < A.length; i++) {
        while (A[i] != i+1) {
            if (A[i] <= 0 || A[i] > A.length || A[i] == A[A[i] - 1]) {
                break;
            }

            int tmp = A[A[i]-1];
            A[A[i]-1] = A[i];
            A[i] = tmp;
        }
    }

    for (int i = 0; i < A.length; i++) {
        if (A[i] != i+1) {
            return i+1;
        }
    }
    return A.length+1;
     
}
  
  //Working!!!!
  public static int firstMissingPositive(int[] A) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int split = shift(A);
    int[] B = Arrays.copyOfRange(A, split, A.length);
    for(int i = 0; i < B.length; i++)
    {
      if(Math.abs(B[i]) - 1 < B.length && B[Math.abs(B[i]) - 1 ] > 0)
        B[Math.abs(B[i]) - 1] = -B[Math.abs(B[i]) - 1];
    }
   
    // Return the first index value at which is positive
    for(int i = 0; i < B.length; i++)
      if (B[i] > 0)
        return i+1;  // 1 is added becuase indexes start from 0
   
    return A.length - split + 1;
  }
  
  
  public static int shift(int[] A){
    int j = 0;
    for(int i = 0; i< A.length; i++){
      if(A[i] <= 0){
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
        j++;
      }
    }
    return j;
  }

  
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] A=new int[]{0};
    System.out.println(firstMissingPositive1(A));
  }

}
